package com.banding.algorithm;

public class Recursion {
    public static int factorial(int i) {
        if (i < 1) {
            throw new RuntimeException("i要大于等于1");
        }
        if (i == 1) {
            // 存在基本情况
            return 1;
        }
        // 存在递推关系
        return i * factorial(i - 1);

    }

    public static int fib(int i) {
        if (i < 1) {
            throw new RuntimeException("i要大于等于1");
        }
        if (i <= 2) {
            // 存在基本情况
            return 1;
        }
        // 存在递推关系
        return fib(i - 2) + fib(i - 1);

    }

    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        if (n <= 2) {
            return true;
        }
        if (n % 2 != 0) {
            return false;
        }

        return isPowerOfTwo(n / 2);
    }
}
